package com.cat.dynamicPlanning;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/palindrome-partitioning/description/
 * @create 2025/9/11 20:05
 * @since JDK17
 */

public class Solution99 {
    int n;
    List<List<String>> ans = new ArrayList<>();
    List<String> path = new ArrayList<>();
    String s;
    void dfs(int cur, int start) {
        if (cur == n) {
            ans.add(new ArrayList<>(path));
            System.out.println(ans.size());
            return;
        }
        // 不分割
        if (cur < n - 1) {
            dfs(cur + 1, start);
        }

        if (judge(start, cur)) {
            path.add(s.substring(start, cur + 1));
            dfs(cur + 1, cur + 1);
            path.remove(path.size() - 1);
        }
    }
    boolean judge(int l, int r) {
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) {
                return false;
            }
        }
        return true;
    }


    public List<List<String>> partition(String s) {
        n = s.length();
        this.s = s;
        dfs(0, 0);
        return ans;
    }
}
